#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int quick_sort(int *array, unsigned n);
void Swap(int *a, int *b);
int Median3(int A[], int Left, int Right);
int _quick_sort(int *array, int Left, int Right);

int main(int argc, char *argv[])
{
    unsigned amount = 0;
    FILE *file;

    if (argc > 1)
    {
        file = fopen(argv[1], "r");
        if (!file)
        {
            printf("Fail to open %s\n", argv[1]);
            exit(-1);
        }
    }
    else
        file = stdin;

    fscanf(file, "%u", &amount);
    int *array = malloc(sizeof(int) * amount);
    if (!array)
    {
        printf("malloc failed!\n");
        exit(-2);
    }
    for (unsigned i = 0; i < amount; i++)
        fscanf(file, "%d", array + i);
    quick_sort(array, amount);

    printf("%d", *array);
    for (unsigned i = 1; i < amount; i++)
        printf(" %d", *(array + i));
    exit(0);
}
int quick_sort(int *array, unsigned n)
{
    _quick_sort(array,0,n-1);
    return 0;
}
void Swap(int *a, int *b)
{
    int c = *a;
    *a = *b;
    *b = c;
}

int Median3(int A[], int Left, int Right)
{
    int Center = (Left + Right) / 2;
    if (A[Left] > A[Center])
        Swap(&A[Left], &A[Center]);
    if (A[Left] > A[Right])
        Swap(&A[Left], &A[Right]);
    if (A[Center] > A[Right])
        Swap(&A[Center], &A[Right]);
    /* 此时A[Left] <= A[Center] <= A[Right] */
    Swap(&A[Center], &A[Right - 1]); /* 将基准Pivot藏到右边*/
    /* 只需要考虑A[Left+1] … A[Right-2] */
    return A[Right - 1]; /* 返回基准Pivot */
}

int _quick_sort(int *array, int Left, int Right)
{
    if(Right-Left <0) return 0;
    int pivot, low, high;
    pivot = Median3(array, Left, Right);
    low = Left;
    high = Right - 1;
    while (1)
    {
        while (array[++low] < pivot);
        while (array[--high] > pivot);
        if(low>high) Swap(&array[low],&array[high]);
        else break;
    }
    Swap(array+low,array+Right-1);
    _quick_sort(array,Left,low-1);
    _quick_sort(array,low+1,Right);
    return 0;
}
